﻿//一个数组实现两个栈
// 注意下，当题中用函数实现时，栈顶指针都是指向其数组的下标
//Stack CreateStack(int MaxSize) {
//    Stack S = (Stack)malloc(sizeof(struct SNode));
//    if (!S) {
//        perror("S malloc");
//        exit(-1);
//    }
//    S->Data = (ElementType*)malloc(sizeof(ElementType) * MaxSize);
//    if (!S->Data) {
//        perror("S->Data malloc");
//        exit(-1);
//    }
//    S->MaxSize = MaxSize;
// //用一个数组实现两个栈时，将考虑将从开始起插入Top,从末尾起插入Top2
//    S->Top1 = -1;
//    S->Top2 = MaxSize;
//    return S;
//}
//bool Push(Stack S, ElementType X, int Tag) {
//    if (S->Top1 + 1 == S->Top2) {
//        puts("Stack Full");
//        return false;
//    }
//    if (Tag == 1) {
//        S->Data[++S->Top1] = X;
//    }
//    if (Tag == 2) {
//        S->Data[--S->Top2] = X;
//    }
//    return true;
//}
//ElementType Pop(Stack S, int Tag) {
//    if ((Tag == 1 && S->Top1 == -1) || (Tag == 2 && S->Top2 == S->MaxSize)) {
//        fprintf(stdout, "Stack %d Empty\n", Tag);
//        return ERROR;
//    }
//    if (Tag == 1) {
//        return S->Data[S->Top1--];
//    }
//    if (Tag == 2) {
//        return S->Data[S->Top2++];
//    }
//}

//bool isEmpty() {
//    if (top == -1) {
//        return true;
//    }
//    return false;
//}
//void Push(int x) {
//    if (top == MaxSize - 1) {
//        return;
//    }
//    mystack[++top] = x;
//}
//int getTop() {
//    if (top == -1) {
//        return -1;
//    }
//    return mystack[top];
//}
//void Pop() {
//    if (top == -1) {
//        return;
//    }
//    top--;
//}

//bool Push(Stack S, ElementType X) {
//    if (S->Top == S->MaxSize) {
//        fprintf(stdout, "Stack Full\n");
//        return false;
//    }
//    S->Data[S->Top++] = X;
//    return true;
//}
//ElementType Pop(Stack S) {
//    if (S->Top == 0) {
//        fprintf(stdout, "Stack Empty\n");
//        return ERROR;
//    }
//    S->Top--;
//    return S->Data[S->Top];
//}

//#include<stdio.h>
//#include<malloc.h>
//typedef struct data {
//    int n;
//    char a, b, c;
//}Hanoi;
//typedef struct Stack {
//    Hanoi data[1000];
//    int top;
//}Stack;
//void Init(Stack* s) {
//    s->top = -1;
//}
//void push(Stack* s, Hanoi h) {
//    s->data[++s->top] = h;
//}
//void pop(Stack* s) {
//    s->top--;
//}
//Hanoi top(Stack* s) {
//    return s->data[s->top];
//}
//int isEmpty(Stack* s) {
//    if (s->top == -1) {
//        return 1;
//    }
//    return 0;
//}
//void initHanoi(Hanoi* h, char a, char b, char c, int n) {
//    h->a = a;
//    h->b = b;
//    h->c = c;
//    h->n = n;
//}
//int main() {
//    int n;
//    Stack* s;
//    s = (Stack*)malloc(sizeof(Stack));
//    while (scanf("%d", &n) != EOF) {
//        Init(s);
//        Hanoi h, temp;
//        initHanoi(&h, 'a', 'b', 'c', n);
//        push(s, h);
//        while (!isEmpty(s)) {
//            h = top(s);
//            pop(s);
//            if (h.n == 1) {
//                printf("%c -> %c\n", h.a, h.c);
//                continue;
//            }
//            initHanoi(&temp, h.b, h.a, h.c, h.n - 1);
//            push(s, temp);
//            initHanoi(&temp, h.a, h.b, h.c, 1);
//            push(s, temp);
//            initHanoi(&temp, h.a, h.c, h.b, h.n - 1);
//            push(s, temp);
//        }
//    }
//}